package com.cat.graphTheory;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/description/
 * @create 2025/9/19 20:13
 * @since JDK17
 */

public class Solution16 {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        int n = recipes.length;
        List<String> ans = new ArrayList<>();
        Map<String, List<String>> g = new HashMap<>();
        Map<String, Integer> in = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (var s : ingredients.get(i)) {
                g.computeIfAbsent(s, k -> new ArrayList<>()).add(recipes[i]);
                in.merge(recipes[i], 1, Integer::sum);
            }
        }

        Deque<String> q = new ArrayDeque<>();
        for (String supply : supplies) {
            q.offer(supply);
        }
        while (!q.isEmpty()) {
            var x = q.poll();
            if (g.get(x) == null) {
                continue;
            }
            for (var y : g.get(x)) {
                if (in.merge(y, -1, Integer::sum) == 0) {   //
                    q.offer(y);
                }
            }
        }

        for (String recipe : recipes) {
            if (in.get(recipe) == 0) {
                ans.add(recipe);
            }
        }
        return ans;
    }
}
